---
title: "（70分）外卖店优先级"
created: 2025-11-28
tags:
  - 算法
---

# （70分）外卖店优先级

## 题目 [外卖店优先级](https://www.acwing.com/problem/content/1243/)

![[image-743f476e.png]]

## 思路分析

直接模拟能拿70分 考试时可能就只能到这里了

确实乍一看没找到能优化的点

把订单全都存起来 按时间处理 若某时间某店有订单 就加上订单数\*2 若没订单 就--

超过5 加入缓存 变得小于等于3 移除

因为这里卡在了空间上 所以尝试用可变长数组来优化空间

然后emm 痛苦转移

超时了 还是过了7个

白改

正解有点麻烦 懒得看了 这种模拟题大概我就做到这 懒得想后面的了

![[image-f94afde9.png]]

## 代码实现

7/10 mle

```cpp
#include <bits/stdc++.h>

using namespace std;

const int Maxsize = 10010;

unordered_map<int, unordered_map<int, int>> orders;

int priority[Maxsize];

bool inCache[Maxsize];

int N, M, T;

int main() {

    cin >> N >> M >> T;

    while (M--) {

        int ts, id;

        cin >> ts >> id;

        orders[ts][id]++;

    }

    for (int i = 1; i <= T; i++) {

        for (int j = 1; j <= N; j++) {

            if (orders[i][j] > 0)

                priority[j] += 2 * orders[i][j];

            else if (priority[j] > 0)

                priority[j]--;

            if (priority[j] > 5)

                inCache[j] = true;

            else if (priority[j] <= 3)

                inCache[j] = false;

        }

    }

    int res = 0;

    for (int i = 1; i <= N; i++)

        res += inCache[i];

    cout << res;

    return 0;

}
```

7/10 tle

```cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e5+10;

int main() {

    int n, m, T;

    cin >> n >> m >> T;

    vector<int> priority(n+1, 0);

    vector<bool> inCache(n+1, false);

    unordered_map<int, unordered_map<int, int>> orders;

    for (int i = 0; i < m; i++) {

        int ts, id;

        cin >> ts >> id;

        orders[ts][id]++;

    }

    for (int i = 1; i <= T; i++) {

        // 如果在该时刻有订单

        if (orders.find(i) != orders.end()) {

            // 更新所有在该时刻有订单的店铺的优先级

            for (auto &order : orders[i]) {

                int id = order.first;

                int count = order.second;

                priority[id] += 2 * count;

                if (priority[id] > 5) {

                    inCache[id] = true;

                } else if (priority[id] <= 3) {

                    inCache[id] = false;

                }

            }

        }

        // 对于在该时刻没有订单的店铺，降低优先级

        for (int j = 1; j <= n; j++) {

            if (orders[i].find(j) == orders[i].end() && priority[j] > 0) {

                priority[j]--;

                if (priority[j] <= 3) {

                    inCache[j] = false;

                }

            }

        }

    }

    int result = count(inCache.begin() + 1, inCache.end(), true);

    cout << result;

    return 0;

}
```

```cpp
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define x first

#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n, m, T;

int score[N], last[N];

bool st[N];

PII order[N];

int main()

{

    scanf("%d%d%d", &n, &m, &T);

    for (int i = 0; i < m; i ++ )

        scanf("%d%d", &order[i].x, &order[i].y);

    sort(order, order + m);

    for (int i = 0; i < m;)

    {

        int j = i;

        while (j < m && order[j] == order[i])

            j ++ ;

        int t = order[i].x, id = order[i].y, cnt = j - i;

        i = j;

        score[id] -= t - last[id] - 1;

        if (score[id] < 0)

            score[id] = 0;

        if (score[id] <= 3)

            st[id] = false; // 以上处理的是t时刻之前的信息

        score[id] += cnt * 2;

        if (score[id] > 5)

            st[id] = true;

        last[id] = t;

    }

    for (int i = 1; i <= n; i ++ )

        if (last[i] < T)

        {

            score[i] -= T - last[i];

            if (score[i] <= 3)

                st[i] = false;

        }

    int res = 0;

    for (int i = 1; i <= n; i ++ )

        res += st[i];

    printf("%d\n", res);

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[错误票据|错误票据]] 🏠 [[00-刷题理模型]] ➡️ [[BFS|BFS]]